//
// Created by Langingsing on 2021/10/24.
//

#ifndef PROJ_QUEUE_H
#define PROJ_QUEUE_H

#include "Linear.h"
#include <cstring>

template<typename T>
class Queue : public Linear<T>
{
public:
    Queue();

    /// 入队，返回是否入队成功
    inline bool push(T const &item);

    /// 出队，返回弹出的值，若队为空，抛出错误
    inline T pop();

    /// 获取队列中第一个元素的值，若队为空，抛出错误
    inline T head() const;

    /// 获取队列中最后一个元素的值，若队为空，抛出错误
    inline T tail() const;

private:
    size_t _headIdx; // 队头元素索引

    bool _expandCapacity();

    inline size_t _tailIdx() const;
};

template<typename T>
Queue<T>::Queue()
{
    _headIdx = this->_capacity - 1;
}

template<typename T>
inline bool Queue<T>::push(T const &item)
{
    if (this->_full()) { // 满了
        const bool success = _expandCapacity(); // 扩容

        if (!success) // 扩容失败
            return false;
    }

    this->_size++;
    this->_basePtr[_tailIdx()] = item; // 只有当 1.没满 或 2.满了且扩容成功 才会执行此行
    return true;
}

template<typename T>
inline T Queue<T>::pop()
{
    if (this->empty()) {
        const std::string msg = "no item for pop()";
        throw std::out_of_range(msg);
    }

    const size_t oldIndex = _headIdx;

    ++_headIdx; // 队头后移
    if (_headIdx >= this->_capacity) // 超限
        _headIdx = 0; // 修正为0，实现循环队列

    this->_size--; // 出队，size减小
    return this->_basePtr[oldIndex];
}

template<typename T>
inline T Queue<T>::head() const
{
    if (this->empty()) {
        const std::string msg = "no item for head()";
        throw std::out_of_range(msg);
    }

    return this->_basePtr[_headIdx];
}

template<typename T>
inline T Queue<T>::tail() const
{
    if (this->empty()) {
        const std::string msg = "no item for tail()";
        throw std::out_of_range(msg);
    }

    return this->_basePtr[_tailIdx()];
}

template<typename T>
inline bool Queue<T>::_expandCapacity()
{
    const size_t umax = std::numeric_limits<size_t>::max();
    const ssize_t max = std::numeric_limits<ssize_t>::max();

    if (umax == this->_capacity) // 到达极限
        return false;

    const size_t
            newCapacity = this->_capacity > max
                          ? umax                     // 扩容至size_t的最大值
                          : (this->_capacity << 1u) + 1;   // 扩容至两倍再加一

    T *newBase = (T *) malloc(newCapacity * sizeof(T)); // 重新分配内存

    if (nullptr == newBase) // 分配失败
        return false;

    // 循环队列的复制分为两个片段，以头索引为分隔
    // 计算后半段长度
    const size_t fromHeadToArrayEnd = this->_capacity - _headIdx;
    // 1. 复制后半段
    memcpy(newBase, this->_basePtr + _headIdx, fromHeadToArrayEnd);
    // 2. 复制前半段
    memcpy(newBase + fromHeadToArrayEnd, this->_basePtr, _headIdx);

    free(this->_basePtr); // 释放旧内存

    this->_basePtr = newBase;         // 重新赋值
    this->_capacity = newCapacity;    // 重设容量
    _headIdx = 0;                     // 重设头索引
    return true;
}


template<typename T>
inline size_t Queue<T>::_tailIdx() const
{
    const size_t total = _headIdx + this->_size;
    if (0 == total)
        // 若空队且headIdx为0，令队尾索引为(capacity - 1)，指向线性表的最后一个元素
        return this->_capacity - 1;

    size_t tailElemIdx = total - 1; // 减一以返回队尾元素索引
    if (tailElemIdx >= this->_capacity) // 超限
        tailElemIdx -= this->_capacity; // 修正

    return tailElemIdx;
}

#endif //PROJ_QUEUE_H
